r"""
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/introduction-to-data-structure-binary-search-tree/xpcnds/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        from examples.二叉树的层序遍历 import Solution
        s = Solution()
        return str(s.level_order(self))


class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return root
        if root.val == key:
            if root.right:
                root.val = self.find_left(root.right)
                root.right = self.deleteNode(root.right, root.val)
            elif root.left:
                return root.left
            else:
                root = None
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
        return root

    def find_left(self, cur: TreeNode) -> int:
        while cur.left:
            cur = cur.left
        return cur.val

    def find_right(self, cur: TreeNode) -> TreeNode:
        while cur.right:
            cur = cur.right
        return cur.val


if __name__ == '__main__':
    tree = TreeNode(5)
    tree.left = TreeNode(3)
    tree.left.left = TreeNode(2)
    tree.left.right = TreeNode(4)
    tree.right = TreeNode(6)
    tree.right.right = TreeNode(7)
    s = Solution()
    print(s.deleteNode(tree, 3))

